#pragma once

#include<cassert>
#include<cstdio>
#include<iostream>
#include<set>
#include<string>
#include<vector>

using namespace std;

class IGraph
{
public:
	virtual string graph_representation() const = 0;
	virtual int get_vertices_number() const = 0;
	virtual int get_edges_number() const = 0;
	virtual bool is_edge(int vertex_from, int vertex_to) const = 0;
	virtual vector<int> get_incidence_list(int vertex) const = 0;

	virtual ~IGraph() {}
};

class MatrixGraph : public IGraph
{
	int vertices_number_;
	int edges_number_;
	vector<vector<bool>> adjacency_matrix_;
public:
	MatrixGraph(int vertices_number, const vector<pair<int, int>>& edges);
	string graph_representation() const
	{
		return "Matrix";
	}
	int get_vertices_number() const
	{
		return vertices_number_;
	}
	int get_edges_number() const
	{
		return edges_number_;
	}
	bool is_edge(int vertex_from, int vertex_to) const
	{
		return adjacency_matrix_[vertex_from][vertex_to];
	}
	vector<int> get_incidence_list(int vertex) const;
};

MatrixGraph::MatrixGraph(int vertices_number, const vector<pair<int, int>>& edges)
{
	vertices_number_ = vertices_number;
	edges_number_ = 0;
	vector<bool> empty(vertices_number);
	adjacency_matrix_.resize(vertices_number, empty);
	for (int edge_number = 0; edge_number < edges.size(); ++edge_number)
	{
		pair<int, int> current_edge = edges[edge_number];
		if (! adjacency_matrix_[current_edge.first][current_edge.second])
			++edges_number_;
		adjacency_matrix_[current_edge.first][current_edge.second] = true;
	}
}

vector<int> MatrixGraph::get_incidence_list(int vertex) const
{
	vector<int> incidence_vertices;
	for (int other_vertex = 0; other_vertex < vertices_number_; ++other_vertex)
		if (adjacency_matrix_[vertex][other_vertex])
			incidence_vertices.push_back(other_vertex);
	return incidence_vertices;
}

class ListGraph : public IGraph
{
	int vertices_number_;
	int edges_number_;
	vector<vector<int>> incidence_list;
public:
	ListGraph(int vertices_number, const vector<pair<int, int>>& edges);
	string graph_representation() const
	{
		return "List";
	}
	int get_vertices_number() const
	{
		return vertices_number_;
	}
	int get_edges_number() const
	{
		return edges_number_;
	}
	bool is_edge(int vertex_from, int vertex_to) const;
	vector<int> get_incidence_list(int vertex) const
	{
		return incidence_list[vertex];
	}
};

ListGraph::ListGraph(int vertices_number, const vector<pair<int, int>>& edges)
{
	vertices_number_ = vertices_number;
	edges_number_ = edges.size();
	vector<int> empty;
	incidence_list.resize(vertices_number, empty);
	for (int edge_number = 0; edge_number < edges.size(); ++edge_number)
	{
		pair<int, int> current_edge = edges[edge_number];
		incidence_list[current_edge.first].push_back(current_edge.second);
	}
}

bool ListGraph::is_edge(int vertex_from, int vertex_to) const
{
	for (int i = 0; i < incidence_list[vertex_from].size(); ++i)
		if (incidence_list[vertex_from][i] == vertex_to)
			return true;
	return false;
}

template <class bfs_functor>
void put_vertex_in_bfs_queue(int vertex_from, int vertex_to, vector<int>* queue, vector<bool>* used, const IGraph* graph, bfs_functor* f)
{
	queue->push_back(vertex_to);
	(*used)[vertex_to] = true;
	f->on_queue(graph, vertex_from, vertex_to);
}

template <class bfs_functor>
void bfs(const IGraph* graph, int start_vertex, bfs_functor* f)
{
	int vertices_number = graph->get_vertices_number();
	assert(start_vertex >= -1 && start_vertex < vertices_number);
	vector<int> queue;
	vector<bool> used(vertices_number, false);
	f->clear(graph);
	if (vertices_number > 0)
	{
		if (start_vertex == -1)
			put_vertex_in_bfs_queue(-1, 0, &queue, &used, graph, f);
		else
			put_vertex_in_bfs_queue(-1, start_vertex, &queue, &used, graph, f);
	}
	int left = 0, last_unused_vertex = 1;
	while (left < queue.size())
	{
		int current_vertex = queue[left];
		++left;
		vector<int> incidence = graph->get_incidence_list(current_vertex);
		for (int i = 0; i < incidence.size(); ++i)
		{
			int adjacent_vertex = incidence[i];
			if (! used[adjacent_vertex])
				put_vertex_in_bfs_queue(current_vertex, adjacent_vertex, &queue, &used, graph, f);
		}
		if (left >= queue.size() && start_vertex == -1)
		{
			while (last_unused_vertex < vertices_number && used[last_unused_vertex])
				++last_unused_vertex;
			if (last_unused_vertex < vertices_number)
				put_vertex_in_bfs_queue(-1, last_unused_vertex, &queue, &used, graph, f);
		}
	}
	return;
}

template <class dfs_functor>
void put_vertex_in_dfs_stack(int vertex_from, int vertex_to, vector<int>* call_stack, const vector<int>& color, const IGraph* graph, dfs_functor* f)
{
	f->on_stack(graph, vertex_from, vertex_to);
	if (color[vertex_to] == 0)
		call_stack->push_back(vertex_to);
}

template <class dfs_functor>
void dfs(const IGraph* graph, int start_vertex, dfs_functor* f)
{
	int vertices_number = graph->get_vertices_number();
	assert(start_vertex >= -1 && start_vertex < vertices_number);
	vector<int> call_stack;
	vector<int> color(vertices_number, 0);
	f->clear(graph);
	if (vertices_number > 0)
	{
		if (start_vertex == -1)
			put_vertex_in_dfs_stack(-1, 0, &call_stack, color, graph, f);
		else
			put_vertex_in_dfs_stack(-1, start_vertex, &call_stack, color, graph, f);
	}
	int last_unused_vertex = 1;
	while (call_stack.size() > 0)
	{
		int current_vertex = call_stack[call_stack.size() - 1];
		if (color[current_vertex] == 0)
		{
			color[current_vertex] = 1;
			f->on_gray(graph, current_vertex);
			vector<int> incidence = graph->get_incidence_list(current_vertex);
			for (int i = 0; i < incidence.size(); ++i)
				put_vertex_in_dfs_stack(current_vertex, incidence[i], &call_stack, color, graph, f);
		}
		else
		{
			if (color[current_vertex] == 1)
			{
				color[current_vertex] = 2;
				f->on_black(graph, current_vertex);
			}
			call_stack.pop_back();
		}
		if (call_stack.empty() && start_vertex == -1)
		{
			while (last_unused_vertex < vertices_number && color[last_unused_vertex] > 0)
				++last_unused_vertex;
			if (last_unused_vertex < vertices_number)
				put_vertex_in_dfs_stack(-1, last_unused_vertex, &call_stack, color, graph, f);
		}
	}
	return;
}

class top_sort_functor
{
	bool cycle_;
	int current_time_;
	vector<int> color_;
	vector<int> out_time_;
public:
	top_sort_functor() {}
	void clear(const IGraph* graph)
	{
		cycle_ = false;
		current_time_ = 0;
		color_.resize(graph->get_vertices_number(), 0);
		out_time_.resize(graph->get_vertices_number(), -1);
	}

	void on_stack(const IGraph* graph, int vertex_from, int vertex_to)
	{
		if (vertex_from != vertex_to && color_[vertex_to] == 1)
			cycle_ = true;
	}
	void on_gray (const IGraph* graph, int vertex)
	{
		color_[vertex] = 1;
	}
	void on_black (const IGraph* graph, int vertex)
	{
		color_[vertex] = 2;
		out_time_[vertex] = current_time_;
		++current_time_;
	}

	bool is_cycle() const
	{
		return cycle_;
	}
	int out_time(int vertex) const
	{
		return out_time_[vertex];
	}

	~top_sort_functor() {}
};

pair <bool, vector<int> > top_sort_vertices(const IGraph* graph)
{
	int vertices_number = graph->get_vertices_number();
	vector<int> sorted_vertices;
	top_sort_functor f;
	dfs(graph, -1, &f);
	if (f.is_cycle())
	{
		pair <bool, vector<int> > answer(false, sorted_vertices);
		return answer;
	}
	sorted_vertices.resize(vertices_number);
	for (int vertex = 0; vertex < vertices_number; ++vertex)
		sorted_vertices[vertices_number - 1 - f.out_time(vertex)] = vertex;
	pair <bool, vector<int> > answer(true, sorted_vertices);
	return answer;
}

IGraph* make_compact_graph(int vertices_number, const vector<pair<int, int>>& edges)
{
	int edges_number = edges.size();
	if (8 * (sizeof(vector<vector<int>>) + vertices_number * sizeof(vector<int>) + edges_number * sizeof(int)) >
		8 * (sizeof(vector<vector<bool>>) + vertices_number * sizeof(vector<bool>)) + vertices_number * vertices_number)
	{
		IGraph* compact_graph = new MatrixGraph(vertices_number, edges);
		return compact_graph;
	}
	else
	{
		IGraph* compact_graph = new ListGraph(vertices_number, edges);
		return compact_graph;
	}
	return NULL;
}

IGraph* make_compact_graph_from_matrix(const vector<vector<int>>& adjancy_matrix)
{
	int vertices_number = adjancy_matrix.size();
	vector<pair<int, int> > edges;
	for (int from = 0; from < vertices_number; ++from)
		for (int to = 0; to < vertices_number; ++to)
			if (adjancy_matrix[from][to] == 1)
			{
				pair<int, int> edge(from, to);
				edges.push_back(edge);
			}
	IGraph* graph = make_compact_graph(vertices_number, edges);
	return graph;
}